The present invention relates to methods and apparatus for combining partial products produced by, for example, a Booth multiplier or array multiplier.
Many of the processes performed by information handling systems and the like involve the multiplication of binary numbers. In a multiplication function, there exists a multiplicand and a multiplier. As is well known in the art, binary numbers are multiplied through a process of multiplying the multiplicand by the first bit of the multiplier. Next, the multiplicand is multiplied by the second bit of the multiplier, shifting the result one digit and adding the products. This process is continued until each bit of the multiplier has been multiplied by the multiplicand.
Each of the products produced by multiplying the multiplicand by a bit of the multiplier produces a number which is referred to as a partial product. The partial products generated during the multiplication of the multiplier binary number and the multiplicand binary number may be produced using, for example, a Booth encoding algorithm, an array multiplier, or the like. The resulting product is formed by accumulating the partial products propagating the carries from the rightmost columns to the left. This process is referred to as partial product accumulation.
Conventional approaches for aggregating or accumulating partial products may require a significant number of cycles. As the addition of two N-bit binary numbers is proportional to O(log2(N)), simple addition is not a preferred technique to obtain the summation. There are numerous Carry-Save addition techniques in existence in the prior art to perform the summation of the partial products of a multiplication process. These Carry-Save addition techniques involve the conversion of 3-bit numbers to 2-bit numbers represented by C (carry) and S (sum). This conversion is sometimes referred to as 3 to 2 compression. The 3 to 2 compressors may be cascaded to obtain higher order compressors, such as 4 to 2 compressors. 3 to 2 compressors and 4 to 2 compressors may in turn be cascaded to obtain even higher order compressors, which are called reduction arrays.
It has been discovered that the propagation delay through a reduction array may significantly impact the throughput of a processing system, particularly where there are a large number of partial products to be computed. Thus, a need has now been identified for a reduction array technique that enjoys a lower propagation delay as compared with conventional implementations.